package com.jhy.review.paixu;

/**
 * @author go_jhy
 * @create 2022/5/19 - 下午 8:49
 * 用归并的思想求逆序对
 */
@SuppressWarnings("all")
public class Nixudui {

    public static void test01(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }
        process(arr,0,arr.length);
    }
    public static void process(int[] arr,int l,int r){
        if(l==r){
            return;
        }
        int mid = l + ((r - l) >>1 );
        process(arr,l,mid);
        process(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    public static void merge(int[] arr,int l,int m,int r){
        int[] temp = new int[r - l + 1];
        int t = 0;
        //记录左边第一个坐标
        int p =  l;
        //记录右边第一个坐标
        int q = m+1;
        while(p <= m && q <= r){
            temp[t++] = arr[p] <= arr[q]? arr[p++] : arr[q++];
        }
        while(p<=m){
            temp[t++] = arr[p++];
        }
        while(q<=r){
            temp[t++] = arr[q++];
        }

        for (int i = 0; i < temp.length; i++) {
            arr[i+l] = temp[i];
        }
    }

}
